package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

public class Lc560 {

    //前缀和 + 哈希优化
    public int subarraySum(int[] nums, int k) {
        int ans = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] preSum = new int[nums.length + 1]; // preSum[i]= nums[0] +...+num[i-1]
        preSum[0] = 0;
        map.put(0, 1);
        for (int i = 1; i <= nums.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i-1];
            int cnt = map.getOrDefault(preSum[i] - k, 0);
            ans += cnt;
            cnt = map.getOrDefault(preSum[i], 0) + 1;
            map.put(preSum[i], cnt);
        }
        return ans;
    }


    //前缀和暴力
    public int subarraySum2(int[] nums, int k) {
        int[] preSum = new int[nums.length + 1];
        preSum[0] = 0;
        for (int i = 1; i <= nums.length; i++) { // preSum[i]= nums[0] +...+num[i-1]
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }

        int cnt = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j <= nums.length; j++) {
                if (k == preSum[j] - preSum[i])
                    cnt ++;
            }
        }
        return cnt;
    }


}
